IBM model是统计机器翻译(statistical machine translation, SMT)非常经典的模型，虽然到现在已经非常古老了，但是其中的一些核心idea到现在还在被使用与翻译系统中，比如alignment模型。之前上京都大学的自然语言处理的课程时就有接触过，最近研究中有个子问题可能可以借鉴IBM model的一些idea，所以又IBM model翻出来重新看了一遍，这里做一个记录和总结，主要参考Columbia University由Michael Collins主讲的课程COMS W4705: Natural Language Processing的notes。
Introduction
IBM model被提出时主要是用于解决翻译French到English。
$f = f_1, f_2…f_m $表示一个French句子，长度为$m$，$f_i$ for $j \in {1…m}$ 表示句子中第$i$个词。
同样的，定义$e = e_1, e_2…e_l$表示一个英语句子。
在SMT系统中，假设我们有一个训练数据集，也就是一些翻译的例子，每个例子也就是French句子以及对应的翻译的English句子，$(f^{(k)}, e^{(k)})$，表示第k个翻译例子。
The Nosiy-Channel Approch(消息信道模型)
IBM model也是使用noisy-channel模型的一个例子，主要包括两个部分：
- A language model， 用于计算任何英语句子$e$存在的概率$p(e)$，比如我们可以用trigram language model来计算，或者最简单直接的unigram language model。一般language model可以通过大量的English corpus就能直接估计出来。
- A translation model，用于计算给定一个English句子$e$，对应的French句子是$f$的条件概率$p(f|e)$。这个概率的计算方法会在后面的内容介绍，一般是从给定的翻译例子的训练数据中估计出来。给定了English句子$e$后，$p(f|e)$主要由两个选择决定：first，the length of French sentence: $m$；second, a choice of the $m$ words $f_1…f_m$。
这里可能会有很多觉得奇怪，任务不是给定法语句子，要翻译为英语句子嘛，为什么前面的translation model是先给定英语句子，其对应法语句子为$f$的概率。下面会给出解释：
我们最直接的任务的表示是($E$表示所有的英语句子)：
$$\begin{aligned} arg \max_{e\in E} p(e | f) \end{aligned}$$通过贝叶斯规则我们可以转换问题为：
$$\begin{aligned} arg \max_{e\in E} p(e|f) &= arg \max_{e\in E} \frac{p(e, f)}{p(f)}\\ &= arg \max_{e\in E} \frac {p(e)p(f|e)}{\sum_{e} p(e)p(f|e)} \\ &= arg \max_{e\in E} p(e)p(f|e) \end{aligned}$$所以问题就转换为了求：
$$\begin{aligned} e^{*} = arg \max_{e\in E} p(e)p(f|e) \end{aligned}$$也就是前面定义的language model和translation model可以解决的问题。一个可能的翻译$e$的score分为两部分：first，the language-model score $p(e)$，给出一个先验概率用于估计这个句子是个合法的英语句子的概率。second，the translation-model score $p(f|e)$，也就是$f$是$e$的翻译的概率。
之所以把原来的问题转换为求：$e^{*} = arg \max_{e\in E} p(e)p(f|e)$（也就是noisy-channel approach），主要的一个好处是可以引入language model。可以有效的改进翻译结果的fluency和语法的合法程度。
只要解决了提到的两个model的参数估计，就可以得到问题的solution。language-model的score一般比较直接，通过分析大规模的English corpus生成的gram model就可以得到，比如trigram model，bigram model。
所以接下来主要要介绍的是：
- 如何定义translation model $p(f|e)$
- 如果从翻译例子集中估计出translation model的参数。
The IBM Models
Alignments
现在我们来解决modeling条件概率$p(f|e)$的问题，$f=f_1…f_m$以及$e=e_1…e_l$。
前面我们提到过，$p(f|e)$主要由两个选择决定：first，the length of French sentence: $m$；second, a choice of the $m$ words $f_1…f_m$。
为了简化问题，这里我们先假设我们已经有了$p(m|l)$的分布（后面会再次引入并介绍如何估计）。从这里开始，我们固定$m$，然后主要考虑modeling下面的分布：
$$\begin{aligned} p(f_1...f_m|e_1...e_l,m) \end{aligned}$$也就是$e=e_1…e_m$并且Frence句子长度为$m$的条件下，翻译为$f=f_1…f_m$的条件概率。
直接model $p(f_1…f_m|e_1…e_l,m)$是非常难的。IBM model的一个核心idea是引入alignment variables。alignment variables用于将French句子中的每个位置（词）alignment到English sentence的一个位置，$a_1, a_2…a_m$，$a_1=2$表示关联French sentence的第一个位置关联到English sentence的第二个位置。每个alignment variable的取值范围即是English句子的所有位置，也就是$a\in {0,1,…,l}$。本质上alignment variables是用于为每个French word指定其对应的English sentence（可以多个French words可以关联到同一个English word）。
因为直接model $p(f_1…f_m|e_1…e_l,m)$是非常难的，所以我们先定义：
$$\begin{aligned} p(f_1...f_m,a_1...a_m \ |\ e_1...e_l,m) \end{aligned}$$进一步我们可以得到：
$$\begin{aligned} p(f_1...f_m|e_1...e_l,m) = \sum_{a_1=0}^{l}\sum_{a_2=0}^{l}\sum_{a_3=0}^{l}...\sum_{a_m=0}^{l} p(f_1...f_m,a_1...a_m|e_1...e_l) \end{aligned}$$$a_j$用于指定$f_j$ is aligned to $e_i, i=a_j$，直观上也就是$f_j$是由$e_i, i=a_j$翻译而来的。注意$e_0$指定的是特殊的$NULL$ word。
Alignment Models: IBM Model 2
这里我们开始具体介绍如何model上面定义的带有隐含变量(hidden variables)的条件分布：
$$\begin{aligned} p(f_1...f_m|e_1...e_l,m) \end{aligned}$$如何model这个条件分布决定了IBM Model 1和2的不同，IBM Model 1其实是IBM Model 2的一个特例。所以首先我们介绍IBM Model 2。
$E$是一个English words的集合
$F$是一个French words的集合
$X$和$Y$分别用于表示French句子的最大可能长度和English句子的最大可能长度。
- $t(f|e)\text{ for any }f\in F, e\in E\cup{NULL}$，也就是也就是$f$是从$e$生成的条件概率。
- $q(j|i,l,m)\text{ for any }l\in {1…X}, m\in{1…Y}, i\in {1…m}$。$q(j|i,l,m)$可以理解为在English sentence长度为$l$, French句子长度为$m$的条件下，alignment variable $a_i$取值为$j$的条件概率。
这里先给出最终的model，根据IBM Model 2的一些假设（后面会介绍），我们可以得到：
$$\begin{aligned} p(f_1...f_m,a_1...a_m|e_1...e_l,m)=\prod_{i=1}^{m}q(a_i|i,l,m)t(f_i|e_{a_i}) \end{aligned}$$Independence Assumptions in IBM Model 2
$L$为一个随机变量，对应着English sentence的长度。
$M$为一个随机变量，对应着French sentence的长度。
$F_1…F_m$是French句子的words。
$A_1…A_m$是French句子的alignment variables。
我们要model的是：
$$\begin{aligned} p(f_1...f_m,a_1...a_m|e_1...e_l,m) \end{aligned}$$也就是：
$$\begin{aligned} P(F_1=f_1...F_m=f_m,A_1=a_1...A_m=a_m|E_1=e_1...E_l=e_l,L=l,M=m) \end{aligned}$$根据概率chain rule，可以转换为：
$$\begin{aligned} P(F_1=f_1...F_m=f_m,A_1=a_1...A_m=a_m|E_1=e_1...E_l=e_l,L=l,M=m)\\ =P(A_1=a_1...A_m=a_m|E_1=e_1...E_l=e_l,L=l,M=m) \\ \times P(F_1=f_1...F_m=f_m|A_1=a_1...A_m=a_m, E_1=e_1...E_l=e_l,L=l,M=m) \end{aligned}$$进一步的，如果我们假设各个word的alignment是独立的，也就是只依赖于$M$和$L$,
，则可以有：
如果我们假设$F_i$的值只依赖于$E_j, j={a_i}$，那么我们有；
$$\begin{aligned} P(F_1=f_1...F_m=f_m|A_1=a_1...A_m=a_m, E_1=e_1...E_l=e_l,L=l,M=m) \\ = \prod_{i=1}^{m} P(F_i=f_i|F_1=f_1...F_{i-1}=f_{i-1}|A_1=a_1...A_m=a_m, E_1=e_1...E_l=e_l,L=l,M=m) \\ = \prod_{i=1}^{m} P(F_i=f_i|E_{a_i}=e_{a_i}) \end{aligned}$$ $$\begin{aligned} P(F_i=f_i|E_{a_i}=e_{a_i}) = t(f_i|e_{a_i}) \end{aligned}$$这样我们就完成了对前面$p(f_1…f_m,a_1…a_m|e_1…e_l,m)$的model（基于IBM Model 2的一些假设），得到：
$$\begin{aligned} p(f_1...f_m,a_1...a_m|e_1...e_l,m)=\prod_{i=1}^{m}q(a_i|i,l,m)t(f_i|e_{a_i}) \end{aligned}$$剩下的问题就是我们如何从翻译例子训练集中估计出参数$q(ai|i,l,m)$和$t(f_i|e{a_i})$。
Applying IBM Model 2
前面我们以及介绍了IBM Model 2，在进一步介绍如何估计参数之前，我们回顾一下我们将如何应用IBM Model 2用于机器翻译问题。
在第一节我们推导过，我们最终的目标是：
$$\begin{aligned} e^{*} = arg \max_{e\in E} p(e)p(f|e) \end{aligned}$$$p(e)$也就是language model，可以简单的通过分析英语语料库的gram model得到。
$p(f|e)$是translation model，也就是我们前面一直在介绍的如何定义和计算这个model。
通过引入alignment model，我们得到：
$$\begin{aligned} p(f|e) = \sum_{a}p(f,a|e) \end{aligned}$$进一步我们需要model $p(f,a|e)$的分布以及计算方式，也就是我们上一节介绍的，我们根据IBM Model 2的假设最终得到：
$$\begin{aligned} p(f_1...f_m,a_1...a_m|e_1...e_l,m)=\prod_{i=1}^{m}q(a_i|i,l,m)t(f_i|e_{a_i}) \end{aligned}$$当然，下面的问题是NP hard的，但是有多种估计方法：
$$\begin{aligned} e^{*} = arg \max_{e\in E} p(e)p(f|e) \end{aligned}$$除了上面的翻译问题，我们还可以利用IBM Model 2用于找到最有可能的alignment。假设我们已经估计得到参数$t(f|e)$和$q(j|i,l,m)$，给定一个新的翻译例子，我们可以利用前面得到的参数估计最有可能的alignment：
$$\begin{aligned} arg \max{a_1...a_m} p(a1_1...a_m|f_1...f_m,e_1...e_l,m) \end{aligned}$$IBM Model 2的idependent假设使得我们可以很直接的计算的到最有可能的alignment，也就是对于每个alignment variable：
$$\begin{aligned} a_i=arg \max{j\in\{0...l\}} q(j|i,l,m)\times t(f_i|e_j) \end{aligned}$$